home *** CD-ROM | disk | FTP | other *** search
/ Whiteline: delta / whiteline CD Series - delta.iso / vision / povray / tools / povquant / pvquan.doc < prev    next >
Text File  |  1995-11-25  |  20KB  |  476 lines
  1.  
  2.                          PVQUANT Version 1.60
  3.  
  4.                      Colour Quantisation Utilities
  5.  
  6.                               for the
  7.  
  8.                     Persistence of Vision Raytracer
  9.  
  10.  
  11.  
  12.  
  13.  
  14.  
  15.  
  16.  
  17.  
  18.  
  19.  
  20.  
  21.  
  22.  
  23.  
  24.  
  25. Written and Distributed by:  
  26.  
  27. Frank van der Hulst, 101 Epuni St, Lower Hutt, New Zealand 
  28.  
  29. Electronic mail to:  
  30. UseNet:  f_vander@comp.vuw.ac.nz, 
  31.          frank@cit.ac.nz,
  32.          frank@whare.cavebbs.welly.gen.nz 
  33. FidoNet: frank vanderhulst at GenBoard (Node 3:771/160)
  34.  
  35. 01 December 1992
  36. גגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגגג 
  37.  
  38. These programs are freely distributable.  The authors retain the copyright 
  39. to the program but authorizes free distribution by BBS'es, networks, 
  40. magnetic media, etc.  The distributor may charge no more than five dollars 
  41. ($5) U.S.  for this software.  
  42.  
  43. The images and data files generated by these programs are the property of 
  44. the user of the software and may be used for any purpose without 
  45. restriction.  
  46.  
  47. The authors make no guarantees or warranties with these programs and claim 
  48. no responsibility for any damage or loss of time caused by this program.  
  49. Bug reports may be sent to the authors but the authors are under no 
  50. obligation to provide bug fixes, features, or any support for this software.  
  51.  
  52. The following conditions are placed on the use of this program:  
  53.  
  54. 1) That it should not be used as part of any commercial package without the 
  55. explicit written consent of the author.  
  56.  
  57. 2) If you make any changes to the source code, please let me know.  That's 
  58. the way this program was built!  
  59.  
  60. 3) This text file must accompany the program.  
  61.  
  62. This manual is divided into the following sections:  
  63.  
  64. 1) Archive Description 
  65. 2) Getting Started
  66. 3) Command Line Parameters
  67. 4) Output File Format
  68. 5) Source Code Information
  69. 6) Displaying the Images
  70. 7) Animation
  71. 8) Porting to Different Platforms
  72. 2) Background
  73.  
  74. 1) Archive Description 
  75. ~~~~~~~~~~~~~~~~~~~~~~ 
  76. This archive contains C source code for a set of programs to convert image
  77. files produced by DKB-Trace or Persistence of Vision raytracer into a format
  78. suitable for display on a VGA screen, or to GIF format.  It includes
  79. programs to generate a single stereoscopic 3D image from two views of a
  80. scene, as well as programs to produce animation from multiple ray-traced
  81. images.  
  82.  
  83. The programs (or large parts of them) were written by several different 
  84. people.  All of the programs are in the public domain to some extent, with 
  85. some restrictions put on them by their respective authors.  I have collected 
  86. these from various places, ported them to Turbo-C, GNU C, or IBM C Set/2 if 
  87. necessary, and formatted them in a way that I like.  The copyright for each 
  88. program still belongs to its author -- my copyright claim extends only to 
  89. the collection of programs (like the editor of a journal, for example).  
  90.  
  91. QUANT (HECKBERT & OCTREE):  Colour quantisation program which post-processes 
  92. raw or Targa image files produced by the Persistence of Vision Ray Tracer
  93. (PoVRay). Two versions can be compiled:  one uses Heckbert's
  94. median-splitting algorithm, whereas the other uses Octree quantisation.
  95.  
  96. DISPLAY:  Displays either 320x400 or 320x200 images, either 2D, or stereo 
  97. 3D.  3D images require Sega 3D-glasses to be connected to the serial port 
  98. for viewing.  
  99.  
  100. ANIMDAT:  Reads an animation source file (*.VAR), and uses it to generate
  101. data files for the PoV ray tracer.  
  102.  
  103. ANIMGIF:  Produces a .GIF file containing a series of images to be displayed 
  104. by ANIM.  
  105.  
  106. ANIMFLI:  Produces a .FLI file containing a series of images to be displayed 
  107. by a .FLI player (e.g.  Autodesk's AAPLAY).  
  108.  
  109.  
  110.  
  111. 2) Getting Started
  112. ~~~~~~~~~~~~~~~~~~ 
  113. Before quantising an image, you must create one!  Use either DKB-TRACE or
  114. PoVRAY to produce output in the "Targa" format.
  115.  
  116. I use the following command line:  
  117.  
  118. POVRAY -ipacman.dat -opacman.tga -w320 -h400 -v +ft +p +x -a
  119.  
  120. See the raytracer documentation on what all the above mean.  Most important 
  121. is the "+ft" option which tells the raytracer to produce "Targa" files.  The 
  122. quantiser can also read "raw" format files (use the "+fr" switch).  If you 
  123. use this (there's no real reason why you should) and run POVRAY on a PC,
  124. you'll probably need to rename the files produced.  By default it gives 
  125. extensions of .R8, .G8, and .B8, whereas QUANT needs extensions of .RED, 
  126. .GRN, and .BLU.  
  127.  
  128. Now try running the OCTREE quantiser program:  
  129.  
  130. OCTREE pacman 
  131.  
  132. 3) Command Line Parameters
  133. ~~~~~~~~~~~~~~~~~~~~~~~~~~ 
  134. QUANT is a program to convert image files produced by DKB-Trace or
  135. Persistence of Vision raytracer into a format suitable for display on a VGA
  136. screen.  
  137.  
  138. To do this, it must select 256 colours from a palette of 256K colours to 
  139. best represent the colours in the image file which are selected from a 
  140. palette of 16 million.  In other words, it must "quantise" the colours in 
  141. the image file (which are selected from a palette of 16 million) into a set 
  142. of 256 colours selected from a palette of 256K colours.  
  143.  
  144. QUANT is a colour quantisation program which post-processes raw or 
  145. Targa image files produced by the Persistence of Vision Ray Tracer (PoV 
  146. Ray). Two versions can be compiled:  one uses Heckbert's median-splitting
  147. algorithm, whereas the other uses Octree quantisation.  The Heckbert version
  148. takes much longer to run, especially on a 286.  On the other hand, it
  149. produces much better results.  The Octree version is faster, but not as
  150. good.  
  151.  
  152. As an additional feature, the program allows the user to generate a single 
  153. palette from several image files, thus making it possible to produce a 
  154. stereoscopic 3D image from two views of a scene, or animation.  
  155.  
  156. Command line format:  
  157.  
  158. HECKBERT [-C=colours][-W=width][-H=height][-D=display][-T=type] 
  159.          [-O=outputbits][-S=speed][-N=numfiles] file_name
  160.  
  161. or 
  162.  
  163. OCTREE [-C=colours][-W=width][-H=height][-D=display][-T=type] 
  164.        [-O=outputbits][-N=numfiles] file_name
  165.  
  166. If no parameters are given, a usage message is shown.  
  167.  
  168.                                                             Default value
  169. outputbits = bits per colour being output                   [6]
  170. intype = 0 or 1 to select input format                      [0]
  171.             0 selects raw files (.RED, .GRN,.BLU)
  172.             1 selects Targa (.TGA)
  173. type = 0, 1 or 2 to select output format                    [1]
  174.             0 selects 4-planar  output for 320x400 or 320x200 images
  175.             1 selects linear output
  176.             2 selects GIF output.
  177. display = 1 to display while outputting                     [1]
  178.             Only available on the PC.
  179. colours = number of separate colours to produce             [256]
  180. width = number of pixels wide the image is                  [320]
  181. height = number of pixels high the image is                 [200]
  182. speed = 1 or 0 for fast or slow quantisation                [0]
  183.             Heckbert speed switch.  If zero, the program does another pass
  184.             through the data, to find the optimal palette selection.  This
  185.             pass is much slower than the earlier passes, and produces
  186.             slightly better results.
  187. numfiles = number of files to convert                       [1]
  188.             If  numfiles = 1, QUANT calculates a palette for that file and
  189.             writes it to disk with a .2D extension.  
  190.             If numfiles = 2, QUANT calculates one combined palette from both
  191.             images, then writes this palette, as well as the data from
  192.             both files to an output file with a .3D extension.  
  193.             If numfiles > 2, QUANT assumes this is an animation sequence, 
  194.             and generates one palette for all the files, then writes the
  195.             output in the form of several 2D-format files (one for each 
  196.             input file), all with the same palette.  The files are named
  197.             FILE_0.0, FILE_0.1, FILE_0.2, ...
  198.  
  199. file_name   the base part of the filename(s) of files to be converted -- a
  200.             numeric part and an extension are added automatically.  The
  201.             numeric part consists of an underscore followed by a number, and
  202.             the extension will depend on the input file type.  (e.g.  if the
  203.             file_name is PAC and the input type is Targa, the first file 
  204.             read will be PAC_0.TGA.
  205.  
  206. When the final result is to be a .FLI file, it may be better to generate the 
  207. palette for each image separately, since .FLI players can use different 
  208. palettes for each frame.  
  209.  
  210. For example, 
  211.  
  212. C:\>OCTREE GLASS -c=16 
  213.  
  214. will open the files GLASS.RED, GLASS.GRN, and GLASS.BLU, use Octree 
  215. quantisation to find the 16 best colours, then write the output to to the 
  216. file GLASS.2D.  As it creates the file, it will display the image on the 
  217. screen.  
  218.  
  219. C:\>HECKBERT PACMAN -n=2 -c=64 -d=0 
  220.  
  221. will open the files PACMAN_0.RED, PACMAN_0.GRN, and PACMAN_0.BLU, then the 
  222. files PACMAN_1.RED, PACMAN_1.GRN, and PACMAN_1.BLU, then create the file 
  223. PACMAN.3D.  This will be done using Heckbert's median-splitting algorithm.  
  224.  
  225. C:\>HECKBERT PACMAN -i=1 -t=1 
  226.  
  227. will open the file PACMAN.TGA, and create the file PACMAN.2D.  This will be 
  228. done using Heckbert's median-splitting algorithm.  
  229.  
  230. C:\>HECKBERT TEST -n=4 
  231.  
  232. will read the files TEST_0.RED/GRN/BLU, TEST_1.RED/GRN/BLU, etc., then 
  233. create the files TEST_0.0, TEST_0.1, TEST_0.2, and TEST_0.3.  This will be 
  234. done using Heckbert's median-splitting algorithm.  
  235.  
  236. Note that both versions of QUANT require large amounts of memory.  
  237.  
  238.  
  239. 4) Output File Format
  240. ~~~~~~~~~~~~~~~~~~~~~ 
  241. QUANT produces output in one of four possible output formats:  
  242.  
  243. GIF 
  244. 2D -- a single image 
  245. 3D -- two stereoscopic images of the same scene 
  246. nn -- animation 
  247.  
  248. The GIF output file can be displayed using a GIF display program such as 
  249. CSHOW or Image Alchemy.  The 2D and 3D format files can be displayed using 
  250. the provided DISPLAY program.  The animation output is in the form of 
  251. several 2D-format files (one for each input file), all with the same 
  252. palette.  The files are named FILE_1.1, FILE_1.2, FILE_1.3, ...  
  253.  
  254. The 2D and 3D files have the following format:  
  255. 7-byte header 
  256. 256*3-byte palette 
  257. one or two screen images (one byte per pixel).  
  258.  
  259. The header consists of:  
  260.  
  261. <signature> - 2 bytes long, value '2D' or '3D', depending on the image type.  
  262. <num columns> - 2 bytes long (LS byte first) 
  263. <num rows> - 2 bytes long (LS byte first) 
  264. <num colours> - 1 byte 
  265.  
  266. The palette consists of a series of 3-byte fields, each corresponding to the 
  267. combination of blue, green, and red signals for the corresponding colour.  A 
  268. zero value in the <num colours> field represents 256 colours.  
  269.  
  270. A screen image can be in one of two formats:  4-planar or linear 
  271. (corresponding to setting the type command line parameter to 0 or 1).  
  272.  
  273. The  4-planar format was designed to make it fast and easy to display an
  274. image in either 320x400x256 or 320x200x256 mode.  To facilitate this, the
  275. format of screen image(s) is similar to the memory organisation of the VGA
  276. card in that mode.  For any other image size, the program automatically
  277. outputs images in the linear format.  
  278.  
  279. Each byte is used by the VGA card as an index into the palette, which is 
  280. then used to display the correct colour on the screen.  
  281.  
  282. For the 4-planar format of a 320x400 image, each screen image is made up of 
  283. 128,000 bytes, one per pixel.  Because of the memory organisation of the VGA 
  284. card, each image is made up of 4 banks of 32,000 bytes.  A VGA register is 
  285. set, then a bank is loaded into VGA memory.  Each bank consists of 80 bytes 
  286. per scan line by 400 scan lines.  The bytes from the four banks illuminate 
  287. adjacent pixels.  For a 4-planar 320x200 image, the total image size is 
  288. 64,000 bytes, made up of 4 banks of 16,000.  
  289.  
  290. In the linear format, each byte in turn is stored.  
  291.  
  292. 5) Source Code Information
  293. ~~~~~~~~~~~~~~~~~~~~~~~~~~ 
  294. This program is the amalgamation of several pieces of work by different
  295. authors:  
  296.  
  297. The colour quantisation algorithms used in QUANT come from two sources:  
  298.  
  299. 1.  The files OCTREE.C and OCTREE.H are based on code written by Wolfgang
  300. Stuerzlinger who placed it in the public domain.  The code implements the 
  301. algorithm described in:
  302.  
  303. Graphic Gems, edited by Andrew Glassner 
  304. Article:  A Simple Method for Color Quantisation: Octree Quantisation, 
  305. pg. 287 ff by:  Michael Gervautz, Werner Purgathofer
  306.  Technical University, Vienna, Austria
  307.  
  308. 2. The files HECKBERT.C and HECKBERT.H are based on COLORQUANT.C written by 
  309. Craig E Kolb who placed it in the public domain.  
  310.  
  311. The GIF output code is based on code in version 1.1 (Sep.  1990) of Gif-Lib, 
  312. a package written by Gershon Elber.  
  313.  
  314. The FLI creation code comes from FLI.LIB (Dec 1989) by Jim Kent of Dancing 
  315. Flame, San Francisco.  Following is an excerpt from his README file:  
  316.  
  317. Fli.lib and the associated source and documentation files are Copyright 1990 
  318. Dancing Flame, San Francisco.  Permission is granted to distribute fli.lib 
  319. and to use fli.lib in any non-commercial program.  If you would like to use 
  320. fli.lib in a commercial program please contact Dancing Flame.  The normal 
  321. licensing fee is the retail price of 5 copies of the program you are 
  322. selling.  
  323.  
  324. Dancing Flame 
  325. 3312 16th St.  
  326. San Francisco, CA 94114.  
  327. (415) 861-6119
  328.  
  329. The VGA 320*400 output is based on a program published by Michael Abrash in 
  330. Programmer's Journal.  
  331.  
  332. The VGA 320*200 output is based on a program (FLIPDEMO.ASM) sent to me by K. 
  333. Heidenstrom.  
  334.  
  335. ANIMDAT was written by Todd Sankey (sankey@unixg.ubc.ca), who sent me the 
  336. source code for it. This is largely unchanged from his version, except that
  337. I replaced *.DAT with *.POV.
  338.  
  339. All of the above programs are in the public domain.  
  340.  
  341. I took all these bits and chopped them round a bit to make them work the way 
  342. I like, and added my own code to do things like outputting to my 2D/3D file, 
  343. virtual memory management, handle command line parameters, etc.  
  344.  
  345.  
  346. 6) Displaying the Images
  347. ~~~~~~~~~~~~~~~~~~~~~~~~ 
  348. The DISPLAY program provided will display either 320x400 or 320x200 images,
  349. either 2D, or stereo 3D.  According to Abrash's article, this should work on
  350. any VGA or SVGA card.  (On one machine which has a VGA card, this didn't
  351. work).  It has the following command line options:  
  352.  
  353. Command line format:  
  354.  
  355. DISPLAY FILE1 [FILE2]...  [/W] [/C] [/R] [/H]
  356.  
  357. where FILE1, FILE2...  are the names (with extensions) of files to be 
  358. displayed.  
  359.  
  360. /W => wait after each following image has been displayed 
  361. /C => clear screen after each image 
  362. /R => reverse eye-image sync for following 3D images 
  363. /H => toggle screen height between 400 and 200 line modes
  364.  
  365. Each of these switches acts as a toggle.  The program has the following 
  366. defaults:  wait after each image for a keypress before displaying the next 
  367. clear the screen after each image first image of a 3D-pair is for left eye, 
  368. second is for right eye 400 line mode 
  369.  
  370. 7) Animation
  371. ~~~~~~~~~~~~ 
  372. Two programs are provided to support animation:
  373. 1) ANIMDAT generates .POV files for PoVRay
  374. 2) ANIMFLI converts multiple 2D files into a FLI file
  375.  
  376. ANIMDAT: This program reads an animation source file (*.VAR) and a template
  377. .POV file, and uses them to generate multiple data files for the PoV ray 
  378. tracer.
  379.  
  380. Command format:
  381.  
  382. ANIMDAT filename
  383.  
  384. For more information, read ANIMDAT.DOC, found in the ANIMDAT.ZIP archive.
  385.  
  386. ANIMFLI:  This program produces a .FLI file containing a series of images to 
  387. be displayed.  The images to be read in must be generated by QUANT (either 
  388. version) with the output format set to "type 1" (single plane) Image size 
  389. must be 320x200.  
  390.  
  391. This file can then be read by any standard FLI player to produce animation.  
  392.  
  393. Command line format:  ANIMFLI INPUT_FILE OUTPUT_FILE 
  394.  
  395. where INPUT_FILE is the name (without any extension) of the sequence of 
  396. input files to be loaded into the FLI 
  397.  
  398. OUTPUT_FILE is the name (without extension) of the FLI file to be created.  
  399.  
  400.  
  401. 8) Porting to Different Platforms
  402. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  403. I've tried to make QUANT portable.  So far, it's working out fairly
  404. well. All the programs (except DISPLAY -- it is specific to MS-DOS)
  405. compile cleanly and run properly (no warnings, no errors) using either
  406. Turbo-C++ v1.00, GNU C, or IBM C Set/2.
  407.  
  408. If you want to port QUANT to another system, please try to modify the core 
  409. as little as possible.  
  410.  
  411. Similarly, if you implement a different quantisation algorithm, try to keep 
  412. it as a separate module.
  413.  
  414.  
  415. 9) Background
  416. ~~~~~~~~~~~~~ 
  417. I used to have a 286 PC clone with a VGA screen, and am interested in 
  418. virtual reality.  I knew that a 286 doesn't have the horsepower to be
  419. good for that, but that's all I had.  Attached to this I had a pair of
  420. Sega 3D glasses, which allowed me to view see a 3D image by displaying
  421. stereoscopic pairs of images on the screen.
  422.  
  423. I started off drawing images with Turbo C, but that was time-consuming and 
  424. not very effective.  I then got a copy of DBW_RENDER and used it (over many 
  425. nights over many weeks) to produce images.  In the meantime, Craig Kolb had 
  426. sent me a copy of his COLORQUANT code, which I ported to Turbo C. I also 
  427. found code to display images in 320x400 mode on my VGA.  Finally I could 
  428. display some good images.  I modified the quantiser to read two input files 
  429. to produce one palette, so that I could display a 3D image.  
  430.  
  431. The primitives available in DBW_RENDER were very limited, so I switched to 
  432. DKB-TRACE v2.12.  And ran my machine day and night for months.  
  433.  
  434. Then I got access to a 486 running SCO Unix.  Great!  My 286 took a rest at 
  435. nights, because I could generate the most complex scenes in only a few 
  436. hours.  Unfortunately, I couldn't display the images, or even move them 
  437. easily from the 486 (the only direct interchange medium is 360K floppies, 
  438. and the QRT-format files are too big).  Also working with the QRT-format was 
  439. clumsy, so I converted the quantiser to read raw format files (each of which 
  440. is only 128K long, thus easily transported).  Then I saw a copy of the 
  441. Octree quantisation code on UseNet, so I tried that.  It was much faster (a 
  442. real advantage on the PC) but produced inferior results.  Next step was to 
  443. move the quantiser to Unix, and suddenly the Heckbert technique was best.  
  444.  
  445. The extra speed of the Unix box opened up some new possibilities -- I 
  446. started to look at animation.  I could generate about seven images per hour, 
  447. then use a display program to flip them up one by one.  That works fine 
  448. (although it needs a lot of memory on the PC).  
  449.  
  450. Then I received an assembler source file by K. Heidenstrom which did page 
  451. flipping in 320*200*256 mode.  This makes animation easier, since each image 
  452. requires less memory.  It also makes 3D animation possible.  
  453.  
  454. Then I got access to a Sun IPC workstation than the the '486 -- so I've
  455. ported the raytracer and other files to compile using the GNU C compiler
  456. gcc.  
  457.  
  458. The GIF display program needs lots of memory, and the files (even after GIF 
  459. compression) are huge...  the GIF standard isn't well suited to animation.  
  460. So I took the FLILIB source from Simtel...  that was designed to be compiled 
  461. on the PC using TurboC (included was 8086 assembler source code to open and 
  462. close files, amongst other things).  I ported that to gcc, converting things 
  463. back to C and fixing some annoying pointer addressing problems.  
  464.  
  465. Now I have a '486 on my desk, running OS/2. So I've ported the POV ray 
  466. tracer source code to the IBM C Set/2 compiler, and also the various 
  467. utilities. Todd Sankey also provided a neat animation file generator, which 
  468. fitted in very well with what I was after.
  469.  
  470. Next is Floyd-Steinberg dithering, to remove unwanted "banding" of coloured 
  471. regions (called false contours).  
  472.  
  473. Or maybe adding sound to a FLI player.  Or perhaps 3d animation....  
  474.  
  475.  
  476.